The use of computer graphics has begun to play a large part in our every day lives and activities. For example, many movies feature scenes that contain objects and images that are generated through the use of computer graphics. Computer architecture programs allow users to graphically design buildings and plan landscaping layouts. Several television shows, cartoons and commercials depict animated characters and images through the use of computer graphics.
For many graphical applications, it is desirable for objects to be presented in as realistic a form as possible. One method of producing a realistic image of a particular object is by scanning a picture of the object into memory. Once the object image is scanned into memory, it can be manipulated and graphically displayed as required by the particular application.
For certain graphical applications, a large textured region, such as a section of ocean, a concrete wall, or large area of grass, is needed for a particular scene or setting. For example, a particular architectural design application may require that a large area of grass be displayed for a particular landscaping layout.
One method of applying texture to a region (the “target area”) is through the use of a process known as texture mapping. Texture mapping is generally performed by acquiring a digital image that depicts the texture (“texture image”) that is to be applied to the target area. The texture image may be acquired, for example, by scanning a photograph of something that has the desired texture. Alternatively, the textured image may be created using a computer aided drawing package, such as Microsoft® Paint, or generated as an artificial texture through the use of a computer. Once the texture image has been acquired, one or more “tiles” are generated based on the texture image. The process of creating tiles from a texture image is referred to herein as generating texture tiles. After the textured tiles have been generated, non-overlapping copies of the tiles are applied to the target area in a way that covers the target area.
The process of applying tiles to a particular area is generally referred to as “tiling”. Tiling is performed by covering the target area, without gaps or overlaps, using a closed set of tiles. The pattern in which the tiles are applied is referred to herein as the tiling pattern. The peripheral shapes of the tiles dictate what type of tiling patterns are possible. For example, when rectangular tiles are used, the tiling pattern is typically a rectangular grid.
FIG. 1 illustrates a tile 102 depicting a grass texture that can be used to cover a particular surface for simulating an area of grass. In this example, a single rectangular tile 102 was generated from a texture image. FIG. 2B illustrates a target area 200 covered with copies of tile 102 in a grid-like tiling pattern. The grid-like tiling pattern used to cover target area 200 with copies of tile 102 is an example of the type of periodic tiling patterns used by conventional texture mapping methods.
Periodic tiling patterns are patterns that have both a translational symmetry and a rotational symmetry. Translational symmetry is an invariant isometry in a given direction through a given distance. Isometry is a mapping of the Euclidean plane onto itself which preserves all distances. Symmetry is defined as an isometry that maps any given set onto itself. Thus, if a target area is tiled using a periodic tiling pattern, by starting at a particular point within the target area and taking a finite area of radius “R” around the point, by moving another radius R away, the exact same texture can be found that is contain in the area around the point.
Rotational symmetry, on the other hand, is an invariant isometry about a given point (central rotation) through a given angle.
For example, in FIG. 2A, the tiling of target areas 206 and 208 are respectively performed using translation and rotation symmetry. In this example, tiles at locations 202 and 204 in target area 206 are symmetrically translated to the right to tiling locations 210 and 212, respectively. Conversely, tiles at locations 214 and 216 in target area 208 are symmetrically rotated clockwise for respectively tiling locations 218 and 220. Tiles at locations 202, 204, 210, 212, 214, 216, 218 and 220 have been shaded so that they may be more easily identified. The symmetries apply to the underlying grid expanded infinitely in both horizontal and vertical directions on the page. An infinite square grid translated parallel to one of the sides of a square, by the length of a square's side is identical to the original grid (i.e. a translational symmetry). The same infinite grid rotated a quarter turn clockwise about the corner of any square is identical to the original grid (i.e. rotational symmetry).
A drawback with using conventional texture mapping methods is that the translational symmetry of the tiling patterns cause certain displacements, called “periods”, to be formed. These periods are like repeating puzzle pieces that form repeating sub-patterns that are easily detected over the target area.
For example, as is seen in FIG. 2B, applying tile 102 to target area 200 using a periodic tiling pattern causes a readily discernable rectangular sub-pattern to be produced. This sub-pattern is easily detected by the human eye, thus causing the texture of the target area 200 to appear as a linear repetition of the tiling pattern of tile 102. As a result, the “seams” between the tiles becomes noticeable, thus defeating the goal of creating a region that appears to have a relatively-uniform texture.
In an attempt to reduce the noticeability of seams, some texture mapping methods alternate between using the original tile, and modified images of the tile. The modified images are typically produced by rotating, translating and/or mirroring (i.e. flipping over) the original tile in order to tile the target area. However, because periodic symmetry is inherent in these methods, discernable sub-patterns are also evident on the target areas.
Based on the foregoing, it is highly desirable to provide a mechanism for tiling a target area with a texture image without creating discernable sub-patterns.